package com.company.search;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/word-search/
 * @date 2019/11/21 9:35
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true.
 * 给定 word = "SEE", 返回 true.
 * 给定 word = "ABCB", 返回 false.
 */
public class WordSearch {


    public static void main(String[] args) {
        WordSearch search = new WordSearch();
        System.out.println(search.exist(new char[][]{
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        }, "ABCB"));
    }

    int m,n;

    // 广度优先遍历 写法应该将条件前置
    public boolean search(char[][] board,String s,int i,int j,int index) {

        if(i>=board.length||j>=board[0].length||i<0||j<0||index>=s.length()||s.charAt(index)!=board[i][j]){
            return false;
        }
        if(index==s.length()-1&&s.charAt(index)==board[i][j]){
            return true;
        }

        char temp = board[i][j];
        board[i][j] = '-';
        boolean flag = search(board,s,i-1,j,index + 1) ||
                search(board,s,i, j- 1,index + 1) ||
                search(board,s, i + 1, j,index + 1) ||
                search(board,s,i, j+ 1, index + 1)
                ;
        board[i][j] = temp;

        return flag;
    }

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
               if (search(board,word,i,j,0)) {
                   return true;
               }
            }
        }
        return false;
    }

}
